#include "BTreeNode.h"

using namespace std;


BTLeafNode::BTLeafNode()
{
	memset(buffer, 0, PageFile::PAGE_SIZE);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
 
RC BTLeafNode::read(PageId pid, const PageFile& pf)
{
	
	memset(buffer, 0, PageFile::PAGE_SIZE);
	RC rc = pf.read(pid, buffer);
	return rc;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::write(PageId pid, PageFile& pf)
{
	RC rc = pf.write(pid, buffer);
	return rc;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTLeafNode::getKeyCount()
{
	int num = 0;
	memcpy(&num, &buffer, sizeof(int));

	return num;
}

/*
 * Insert a (key, rid) pair to the node.
 * @param key[IN] the key to insert
 * @param rid[IN] the RecordId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTLeafNode::insert(int key, const RecordId& rid)
{

	// size
	int node_size = sizeof(RecordId) + sizeof(int);
	int total_size = getKeyCount() * node_size;


	// check full
	//
	//
	//
	if(getKeyCount() >= 84) 
	{
		return RC_NODE_FULL;
	}

	char* data = &(buffer[0]);
	int i = 0;


	data = data + sizeof(int) + sizeof(PageId);

	int c_key;
	while(data) 
	{
		memcpy(&c_key, data, sizeof(int));
		if(c_key == 0) 
		{
			break;
		}
		if (c_key < key) 
		{
			data = data + node_size;
			i++;
		} 
		else 
		{
			break;
		}
	}
	// check full
	//
	if (&(buffer[PageFile::PAGE_SIZE]) - data < 20) 
	{
		return RC_NODE_FULL;
	}



	char* temp = (char*)malloc(PageFile::PAGE_SIZE * sizeof(char));
	memset(temp, 0, PageFile::PAGE_SIZE);


	if(total_size > 0) 
	{
		if(c_key !=0)
		{
			memcpy(temp, data, total_size - (node_size * i));
			memset(data, 0, total_size - (node_size * i));
		}
	}



	memcpy(data, &key, sizeof(int));
	data += sizeof(int);
	memcpy(data, &rid, sizeof(RecordId));

	data += sizeof(RecordId);
	if(total_size > 0) 
	{
		if(c_key != 0)
		{
			memcpy(data, temp, total_size - (node_size * i));
		}
	}
	free(temp);

	int c_count = getKeyCount();
	c_count++;





	data = &(buffer[0]);
	memcpy(data, &c_count, sizeof(int));

	return 0;
}

/*
 * Insert the (key, rid) pair to the node
 * and split the node half and half with sibling.
 * The first key of the sibling node is returned in siblingKey.
 * @param key[IN] the key to insert.
 * @param rid[IN] the RecordId to insert.
 * @param sibling[IN] the sibling node to split with. This node MUST be EMPTY when this function is called.
 * @param siblingKey[OUT] the first key in the sibling node after split.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::insertAndSplit(int key, const RecordId& rid, 
                              BTLeafNode& sibling, int& siblingKey)
{
	int node_size = sizeof(RecordId) + sizeof(int);
	int total_size = getKeyCount() * node_size;
	int i = 0;
	int retval = 0;

	char* data = &(buffer[0]);
	data = data + sizeof(int) + sizeof(PageId);

	while(i < (getKeyCount() / 2)) 
	{
		data = data + node_size;
		i++;
	}

	char* temp = (char*)malloc(1024*sizeof(char));
	char* head = temp;
	
	memset(temp, 0, 1024*sizeof(char));
	memcpy(temp, data, total_size - (node_size * (getKeyCount()/2)));


	memset(data, 0, total_size - (node_size * (getKeyCount()/2)));
	int n_key = getKeyCount() / 2;
	memcpy(buffer, &n_key, sizeof(int));

	while(temp) 
	{
		int j;
		RecordId r;
		memcpy(&j, temp, sizeof(int));
		if(j == 0) 
		{
			break;
		}
		temp += sizeof(int);
		memcpy(&r, temp, sizeof(RecordId));
		temp += sizeof(RecordId);
		if(r.sid == 0) 
		{
			if(r.pid == 0)
			{
				if(j !=272)
				{
					int q = r.sid;
				}
			}
		}
		if( sibling.insert(j, r) != 0 ) 
		{
			free(head);
			return RC_FILE_WRITE_FAILED;
		}
	}

	free(head);
	RecordId r;
	if( sibling.readEntry(0, siblingKey, r) != 0) 
	{
		return RC_FILE_READ_FAILED;
	}

	if(key < siblingKey) 
	{
		if( insert(key, rid) != 0 ) 
		{
			return RC_FILE_WRITE_FAILED;
		}
	} 
	else 
	{
		if( sibling.insert(key, rid) != 0 ) 
		{
			return RC_FILE_WRITE_FAILED;
		}
	}

	if( sibling.readEntry(0, siblingKey, r) != 0) 
	{
		return RC_FILE_READ_FAILED;
	}

	return retval; 
}

/*
 * Find the entry whose key value is larger than or equal to searchKey
 * and output the eid (entry number) whose key value >= searchKey.
 * Remeber that all keys inside a B+tree node should be kept sorted.
 * @param searchKey[IN] the key to search for
 * @param eid[OUT] the entry number that contains a key larger than or equalty to searchKey
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::locate(int searchKey, int& eid)
{ 

	int node_size = sizeof(RecordId) + sizeof(int);
	int total_size = getKeyCount() * node_size;
	char* data = &(buffer[0]);
	int c_key;

	int i = 0;

	data = data + sizeof(int);

	while(data) 
	{
		memcpy(&c_key, data, sizeof(int));

		/*if(c_key >= searchKey || c_key == 0) 
		{
			eid = i;
			break;
		}*/

		if(c_key >= searchKey)
		{
			eid = i;
			break;
		}
		if(c_key == 0)
		{
			eid = i;
			break;
		}
		i++;
		data = data + node_size;
	}

	return 0; 
}

/*
 * Read the (key, rid) pair from the eid entry.
 * @param eid[IN] the entry number to read the (key, rid) pair from
 * @param key[OUT] the key from the entry
 * @param rid[OUT] the RecordId from the entry
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::readEntry(int eid, int& key, RecordId& rid)
{ 
	int node_size = sizeof(RecordId) + sizeof(int);
	int total_size = getKeyCount() * node_size;
	char* data = &(buffer[0]);
	int i = 0;

	data = data + sizeof(int) + sizeof(PageId);
	


	while(data && i < eid) 
	{
		data = data + node_size;
		i++;
	}
	memcpy(&key, data, sizeof(int));
	data = data + sizeof(int);
	memcpy(&rid, data, sizeof(RecordId));

	return 0; 
}

/*
 * Return the pid of the next slibling node.
 * @return the PageId of the next sibling node 
 */
PageId BTLeafNode::getNextNodePtr()
{ 
	PageId pid;

	char* data = &(buffer[0]);
	data = data + sizeof(int);

	memcpy(&pid, data, sizeof(PageId));

	return pid; 
}

/*
 * Set the pid of the next slibling node.
 * @param pid[IN] the PageId of the next sibling node 
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTLeafNode::setNextNodePtr(PageId pid)
{ 
	char* data = &(buffer[0]);
	data = data + sizeof(int);

	memcpy(data, &pid, sizeof(PageId));

	return 0; 
}

BTNonLeafNode::BTNonLeafNode() {
	memset(buffer, 0, PageFile::PAGE_SIZE);
}

/*
 * Read the content of the node from the page pid in the PageFile pf.
 * @param pid[IN] the PageId to read
 * @param pf[IN] PageFile to read from
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::read(PageId pid, const PageFile& pf)
{
	RC rc = pf.read(pid, buffer);
	return rc;
}
    
/*
 * Write the content of the node to the page pid in the PageFile pf.
 * @param pid[IN] the PageId to write to
 * @param pf[IN] PageFile to write to
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::write(PageId pid, PageFile& pf)
{
	RC rc = pf.write(pid, buffer);
	return rc;
}

/*
 * Return the number of keys stored in the node.
 * @return the number of keys in the node
 */
int BTNonLeafNode::getKeyCount()
{
	int num = 0;
	memcpy(&num, &buffer, sizeof(int));

	return num;
}


/*
 * Insert a (key, pid) pair to the node.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @return 0 if successful. Return an error code if the node is full.
 */
RC BTNonLeafNode::insert(int key, PageId pid)
{ 

	int node_size = sizeof(PageId) + sizeof(int);
	int total_size = getKeyCount() * node_size;
	char* data = &(buffer[0]);
	int i = 0;

	if(total_size >= PageFile::PAGE_SIZE - node_size) 
	{
		return RC_NODE_FULL;
	}

	data = data + sizeof(int) + sizeof(PageId);

	int c_key;
	while(data) 
	{
		memcpy(&c_key, data, sizeof(int));
		/*if(c_key == 0) 
		{
			break;
		}
		if (c_key < key) 
		{
			data = data + node_size;
			i++;
		} 
		else 
		{
			break;
		}*/
		if(c_key == 0 || c_key >= key)
		{
			break;
		}

		if(c_key <key)
		{
			data = data + node_size;
			i++;
		}
		
	}

	if(c_key == key) 
	{
		data = data + sizeof(int);
		memcpy(data, &pid, sizeof(PageId));
		return 0;
	}

	if (data == &(buffer[PageFile::PAGE_SIZE]))
	{
		return RC_FILE_WRITE_FAILED;
	}

	char* temp = (char*) malloc(PageFile::PAGE_SIZE * sizeof(char));
	memset(temp, 0, PageFile::PAGE_SIZE);


	if(total_size > 0 && c_key != 0) 
	{
		memcpy(temp, data, total_size - (node_size * i));
		memset(data, 0, total_size - (node_size * i));
	}

	memcpy(data, &key, sizeof(int));
	data = data + sizeof(int);
	memcpy(data, &pid, sizeof(PageId));
	data = data + sizeof(PageId);
	if(total_size > 0 && c_key != 0) 
	{
		memcpy(data, temp, total_size - (node_size * i));
	}
	free(temp);

	int c_count = getKeyCount();
	c_count++;
	data = &(buffer[0]);
	memcpy(data, &c_count, sizeof(int));

	return 0;
}

RC BTNonLeafNode::readEntry(int eid, int& key) {
	int node_size = sizeof(PageId) + sizeof(int);
	int total_size = getKeyCount() * node_size;
	int i = 0;

	char* data = &(buffer[0]);
	data = data + sizeof(int);

	while(data) 
	{
		data = data + sizeof(PageId);
		if(i == eid) 
		{
			memcpy(&key, data, sizeof(int));
			break;
		}
		data = data + node_size;
	}

	return 0;
}

/*
 * Insert the (key, pid) pair to the node
 * and split the node half and half with sibling.
 * The middle key after the split is returned in midKey.
 * @param key[IN] the key to insert
 * @param pid[IN] the PageId to insert
 * @param sibling[IN] the sibling node to split with. This node MUST be empty when this function is called.
 * @param midKey[OUT] the key in the middle after the split. This key should be inserted to the parent node.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::insertAndSplit(int key, PageId pid, BTNonLeafNode& sibling, int& midKey)
{ 
	int node_size = sizeof(PageId) + sizeof(int);
	int total_size = getKeyCount() * node_size;
	int i = 0;

	char* data = &(buffer[0]);
	data = data + sizeof(int);

	while(i < (getKeyCount() / 2)) 
	{
		data = data + node_size;
		i++;
	}

	char* temp = (char*) malloc(PageFile::PAGE_SIZE * sizeof(char));
	char* head = temp;
	memset(temp, 0, 1024*sizeof(char));
	memcpy(temp, data, total_size - (node_size * (getKeyCount() / 2)));

	memset(data, 0, total_size - (node_size * (getKeyCount() / 2)));
	int n_key = getKeyCount() / 2;
	memcpy(buffer, &n_key, sizeof(int));

	while(temp) 
	{
		int j;
		PageId p;
		memcpy(&j, temp, sizeof(int));
		if(j == 0) 
		{
			break;
		}
		temp = temp + sizeof(int);
		memcpy(&p, temp, sizeof(PageId));
		temp = temp + sizeof(PageId);
		if( sibling.insert(j, p) != 0) 
		{
			free(head);
			return RC_FILE_WRITE_FAILED;
		}
	}

	free(head);

	if( sibling.readEntry(0, midKey) != 0 ) 
	{
		return RC_FILE_READ_FAILED;
	}

	if(key < midKey) 
	{
		if( insert(key, pid) != 0 )
		{
			return RC_FILE_WRITE_FAILED;
		}
	} 
	else 
	{
		if( sibling.insert(key, pid) != 0 ) 
		{
			return RC_FILE_WRITE_FAILED;
		}
	}

	return 0; 
}

/*
 * Given the searchKey, find the child-node pointer to follow and
 * output it in pid.
 * @param searchKey[IN] the searchKey that is being looked up.
 * @param pid[OUT] the pointer to the child node to follow.
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::locateChildPtr(int searchKey, PageId& pid)
{

	int node_size = sizeof(PageId) + sizeof(int);
	int total_size = getKeyCount() * node_size;
	char* data = &(buffer[0]);
	int c_key;

	data = data + sizeof(int) + sizeof(int);

	while(data) 
	{
		memcpy(&c_key, data, sizeof(int));
		if(c_key != 0) 
		{
			if(c_key < searchKey)
			{
				data = data + sizeof(int);
			}
		} 
		else 
		{
			data = data - sizeof(PageId);
			memcpy(&pid, data, sizeof(PageId));
			break;
		}
		data = data + node_size;
	}
 
	return 0;	
}

/*
 * Initialize the root node with (pid1, key, pid2).
 * @param pid1[IN] the first PageId to insert
 * @param key[IN] the key that should be inserted between the two PageIds
 * @param pid2[IN] the PageId to insert behind the key
 * @return 0 if successful. Return an error code if there is an error.
 */
RC BTNonLeafNode::initializeRoot(PageId pid1, int key, PageId pid2)
{
	char* data = &(buffer[0]);
	int i = 1;
	data = data + sizeof(int);

	memcpy(data, &pid1, sizeof(PageId));
	data = data + sizeof(PageId);
	memcpy(data, &key, sizeof(int));
	data = data + sizeof(int);
	memcpy(data, &pid2, sizeof(PageId));

	memcpy(buffer, &i, sizeof(int));

	return 0; 
}
